import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class ThreeSum {

	public ArrayList<ArrayList<Integer>> threeSum(int[] num) throws Exception {
		HashSet<String> hash = new HashSet<String>();
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		Arrays.sort(num);
		int n = num.length;
		for (int i = n - 1; i >= 0; --i) {
			if (!map.containsKey(num[i]))
				map.put(num[i], i);
		}
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				Integer val = map.get((-num[i] - num[j]));
				if (val != null && val > j) {
					ArrayList<Integer> list = new ArrayList<Integer>();
					list.add(num[i]);
					list.add(num[j]);
					list.add(num[val]);
					res.add(list);
				}
				while (j + 1 < n && num[j + 1] == num[j])
					j++;
			}
			while (i + 1 < n && num[i + 1] == num[i])
				i++;
		}
		return res;
	}

	public static void main(String[] args) throws Exception {
		ThreeSum a = new ThreeSum();
		a.threeSum(new int[] { 0, 4, 5, 1, 1, -9, 8, 3, -1, -2, -3, 2, 1, 9,
				-9, -6, 4, 1 });

	}
}
